package offer;

import sun.reflect.generics.tree.Tree;

@FunctionalInterface
public interface MergeKLists {
    ListNode mergeKLists(ListNode[] lists);
}

/*
    实现思路：败者树，败者树存储败者的下标，用一个数组实现，下标0表示当前的胜者下标，
 */
class MergeKListsImpl1 implements  MergeKLists{
    public static void main(String[] args) {
        ListNode[] TEST_01 = new ListNode[]{
                ListNode.ListNode(new int[]{1,6,8,35}),
                ListNode.ListNode(new int[]{2,4,5,45}),
                ListNode.ListNode(new int[]{3,4,10,20})
        };
        ListNode[] TEST_02 = new ListNode[]{
                ListNode.ListNode(new int[]{1,1,8,10,Integer.MAX_VALUE}),
                ListNode.ListNode(new int[]{1,1,8,10,Integer.MAX_VALUE}),
                ListNode.ListNode(new int[]{1,1,8,10,Integer.MAX_VALUE})
        };
        ListNode[] TEST_03 = new ListNode[]{
                null,
                ListNode.ListNode(new int[]{-1,5,11}),
                null,
                ListNode.ListNode(new int[]{6,10})
        };
        ListNode[] TEST_04 = new ListNode[]{
                ListNode.ListNode(new int[]{1,2,Integer.MAX_VALUE}),
                ListNode.ListNode(new int[]{1,2,Integer.MAX_VALUE}),
                ListNode.ListNode(new int[]{1,2,Integer.MAX_VALUE})
        };

        ListNode[] TEST_05 = new ListNode[]{
                ListNode.ListNode(new int[]{-10,-6,-1}),
                null,
                ListNode.ListNode(new int[]{-10,-7,-4,-2,-2,-1}),
                ListNode.ListNode(new int[]{-10,-9,4}),
                ListNode.ListNode(new int[]{4}),
                ListNode.ListNode(new int[]{-3,1}),
                ListNode.ListNode(new int[]{-8,-3,1,3})
        };
        new MergeKListsImpl1().mergeKLists(TEST_05);
    }
    @Override
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null){
            return null;
        }
        int[] loserTree = new int[lists.length*2];
        initLoserTree(loserTree,lists);
        ListNode fakeHead = new ListNode(0,null), tail = fakeHead;

        int winner = loserTree[0];
        while(true){
            if(lists[winner].val == Integer.MAX_VALUE){
                break;
            }else{
                ListNode temp = lists[winner];
                lists[winner] = lists[winner].next;
                temp.next = tail.next;
                tail.next = temp;
                tail = temp;
                if(lists[winner] == null){
                    lists[winner] = new ListNode(Integer.MAX_VALUE,null);
                }
                winner = adjust(loserTree, lists.length + winner,lists);
            }
        }
        tail.next = null;
        return fakeHead.next;
    }
    void initLoserTree(int[] loserTree,ListNode[] lists){
        int listsLen = lists.length;
        int winner = 0;
        // 初始化loserTree，将数组中的空指针变为最大整数，避免不必要的判空操作
        for (int i = 0; i < listsLen; i++) {
            if(lists[i] != null){
                loserTree[listsLen + i] = i;
            }else{
                lists[i] = new ListNode(Integer.MAX_VALUE);
                loserTree[listsLen + i] = i;
            }
            if(lists[i].val < lists[winner].val){
                winner = i;
            }
        }
        // 前面 listsLen 个节点全部置成假的节点
        for (int i = 0; i < listsLen; i++) {
            loserTree[i] = winner;
        }
        // 从前向后，初始化败者
        for (int i = listsLen; i <= 2 * listsLen - 1; i++) {
            initAdjust(loserTree,i,lists);
        }
    }
    public int adjust(int[] loserTree,int current,ListNode[] lists){
        int winner = loserTree[current];
        int parent = current / 2;
        while(parent > 0){
            if(lists[loserTree[parent]].val <= lists[winner].val){
                int temp = winner;
                winner = loserTree[parent];
                loserTree[parent] = temp;
            }
            current = parent;
            parent = parent / 2;
        }
        loserTree[0] = winner;
        return loserTree[0];
    }

    public int initAdjust(int[] loserTree,int current,ListNode[] lists){
        int winner = loserTree[current];
        int parent = current / 2;
        while(parent > 0){
            if(lists[loserTree[parent]].val <= lists[winner].val){
                if(loserTree[0] != winner) {
                    int temp = winner;
                    winner = loserTree[parent];
                    loserTree[parent] = temp;
                }
            }
            current = parent;
            parent = parent / 2;
        }
        loserTree[0] = winner;
        return loserTree[0];
    }
}